package mashibing.class15;

import java.util.*;

/**
 * 岛屿数量并查集 leetcode200
 */
public class Class15_2_IslandNum {

    // 根据开辟的对象地址    (TODO根据二维数组下标合并)
    public static int numIslands1(char[][] grid) {
        Dot[][] dots = new Dot[grid.length][grid[0].length];
        List<Dot> list = new ArrayList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    Dot dot = new Dot();
                    dots[i][j] = dot;
                    list.add(dot);
                }
            }
        }
        UnionFind1<Dot> unionFind11 = new UnionFind1<>(list);
        // 第一行
        for (int j = 1; j < grid[0].length; j++) {
            if (grid[0][j] == '1' && grid[0][j - 1] == '1') {
                unionFind11.union(dots[0][j], dots[0][j - 1]);
            }
        }

        // 第一列
        for (int i = 1; i < grid.length; i++) {
            if (grid[i][0] == '1' && grid[i - 1][0] == '1') {
                unionFind11.union(dots[i][0], dots[i - 1][0]);
            }
        }

        // 右下角
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    if (grid[i - 1][j] == '1') {
                        unionFind11.union(dots[i][j], dots[i - 1][j]);
                    }
                    if (grid[i][j - 1] == '1') {
                        unionFind11.union(dots[i][j], dots[i][j - 1]);
                    }
                }
            }
        }
        return unionFind11.sets;
    }

    static class UnionFind1<V> {
        // 父亲节点
        public Map<V, V> parent;
        // 每个集合的个数
        public Map<V, Integer> size;
        // 岛屿数量
        public int sets;

        public UnionFind1(List<V> list) {
            parent = new HashMap<>();
            size = new HashMap<>();
            sets = list.size();
            for (V v : list) {
                parent.put(v, v);
                size.put(v, 1);
            }
        }

        public V find(V cur) {
            Stack<V> stack = new Stack<>();
            while (cur != parent.get(cur)) {
                stack.add(cur);
                cur = parent.get(cur);
            }
            while (!stack.isEmpty()) {
                V pop = stack.pop();
                parent.put(pop, cur);
            }
            return cur;
        }

        public void union(V a, V b) {
            V v1 = find(a);
            V v2 = find(b);
            if (v1 != v2) {
                int allSize = size.get(v1) + size.get(v2);
                if (size.get(v1) >= size.get(v2)) {
                    parent.put(v2, v1);
                    size.put(v1, allSize);
                    size.remove(v2);
                } else {
                    parent.put(v1, v2);
                    size.put(v2, allSize);
                    size.remove(v1);
                }
                sets--;
            }
        }
    }

    static class Dot {

    }

    public static void main(String[] args) {
        // [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
        char[][] grid = {{'1','1','1','1','1','0','1','1','1','1'},
                {'1','0','1','0','1','1','1','1','1','1'},
                {'0','1','1','1','0','1','1','1','1','1'},
                {'1','1','0','1','1','0','0','0','0','1'},
                {'1','0','1','0','1','0','0','1','0','1'},
                {'1','0','0','1','1','1','0','1','0','0'},
                {'0','0','1','0','0','1','1','1','1','0'},
                {'1','0','1','1','1','0','0','1','1','1'},
                {'1','1','1','1','1','1','1','1','0','1'},
                {'1','0','1','1','1','1','1','1','1','0'}};
        System.out.println(numIslands1(grid));
    }

}
